#! /usr/bin/env python
# -*- coding: utf-8 -*-

# Copyright (c) Huoty, All rights reserved
# Author: Huoty <sudohuoty@163.com>
# CreateTime: 2020-01-14 18:04:05


class Node(object):
    """双向链表节点"""

    __slots__ = ("data", "next", "prev")

    def __init__(self, data, next=None, prev=None):
        self.data = data  # 数据域
        self.next = next  # 指向后继节点
        self.prev = prev  # 指向前驱节点


class DoubleLink(object):
    """双向链表"""

    def __init__(self):
        self.head = None  # 头指针
        self.tail = None  # 尾指针

    @property
    def length(self):
        probe = self.head
        count = 0
        while probe is not None:
            count += 1
            probe = probe.next
        return count

    def is_empty(self):
        return self.head is None

    def add(self, data):
        """往头部添加数据"""
        node = Node(data)
        node.next = self.head
        if self.is_empty():
            self.tail = node
        self.head = node

    def append(self, data):
        """往尾部添加数据"""
        node = Node(data)
        node.prev = self.tail
        if self.is_empty():
            self.head = self.tail = node
        else:
            self.tail.next = node
            self.tail = node

    def insert(self, index, data):
        """往任意位置插入数据"""
        probe = self.head
        if probe is None or index <= 0:
            self.head = self.tail = Node(data)
        else:
            # 找到第 index - 1 的位置，在其后进行插入
            while index > 1 and probe.next is not None:
                probe = probe.next
                index -= 1
            node = Node(data, probe.next, probe)
            if probe is self.tail:
                self.tail = node
            probe.next = node

    def remove(self, data):
        """删除节点"""
        # 只有一个节点的情况
        if self.head is self.tail:
            self.head = self.tail = None
            return

        probe = self.head
        while probe is not None:
            if probe.data != data:
                probe = probe.next
                continue

            if probe is self.head:
                self.head = probe.next
            elif probe is self.tail:
                probe.prev.next = None
                self.tail = probe.prev
            else:
                probe.prev.next = probe.next
                probe.next.prev = probe.prev
            return

        raise ValueError("{} not in {}".format(data, self))

    def remove_by_index(self, index):
        """通过索引位置删除节点"""
        assert index >= 0
        probe = self.head
        if probe.next is None:  # 只有一个节点的情况
            data = probe.data
            self.head = self.tail = None
        else:
            # 找到第 index 位置上的节点
            while index > 0 and probe.next is not None:
                probe = probe.next
                index -= 1
            data = probe.data
            if probe is self.head:
                self.head = probe.next
            elif probe is self.tail:
                probe.prev.next = None
                self.tail = probe.prev
            else:
                probe.prev.next = probe.next
                probe.next.prev = probe.prev
        return data

        # 以上实现有一个缺陷，当 index 大于链表长度时，默认会删除最后一个
        # 可以通过判断 index 的值是否为 0 来判断是否越界
        # 即当链表已经访问完毕，但 index 还不为 0，则说明 index 越界了
        if probe.next is None and index > 0:
            raise IndexError("index out of range")

    def replace(self, old, new, count=-1):
        probe = self.head
        while probe is not None and count != 0:
            if probe.data == old:
                probe.data = new
                if count > 0:
                    count -= 1
            probe = probe.next

    def travel(self):
        probe = self.head
        while probe is not None:
            print(probe.data)
            probe = probe.next

    def search(self, data):
        probe = self.head
        while probe is not None:
            if probe.data == data:
                return probe.data
            probe = probe.next

    def visit(self, index):
        if self.is_empty():
            raise "{} is empty".format(self)
        if index < 0:
            raise IndexError("index out of range")

        probe = self.head
        while index > 0:
            if probe is None:
                raise IndexError("index out of range")
            probe = probe.next
            index -= 1
        return probe.data


if __name__ == "__main__":
    dl = DoubleLink()
    for i in range(2, 6):
        dl.append(i)
    dl.add(1)
    dl.add(0)
    dl.travel()

    print("")
    dl.insert(3, 10)
    dl.travel()

    dl.remove(10)

    print("remove index 5: ", dl.remove_by_index(5))

    dl.replace(2, 20)
    print("search 20: ", dl.search(20))

    print("")
    dl.travel()
